package com.ljy.my_study.lintcode.二叉查找树中搜索区间;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @author James
 * @date 2018年9月20日
 */
public class TestMain {
	// 描述
	// 给定两个值 k1 和 k2（k1 < k2）和一个二叉查找树的根节点。找到树中所有值在 k1 到 k2 范围内的节点。即打印所有x (k1 <= x <=
	// k2) 其中 x 是二叉查找树的中的节点值。返回所有升序的节点值。
	//
	// 您在真实的面试中是否遇到过这个题？
	// 样例
	// 如果有 k1 = 10 和 k2 = 22, 你的程序应该返回 [12, 20, 22].
	//
	// 20
	// / \
	// 8 22
	// / \
	// 4 12

	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		System.out.println(testMain.searchRange(new TreeNode(5), 6, 10));
	}
	
	public List<Integer> searchRange(TreeNode root, int k1, int k2) {
		if(root==null) return new ArrayList<>();
		List<Integer> list=new ArrayList<>();
		setIntToQueue(list,root,k1,k2);
		Collections.sort(list);
		return list;
	}
	
	private void setIntToQueue(List<Integer> list,TreeNode node,int k1,int k2) {
		if(node==null) return;
		int val=node.val;
		if(k1<=val&&val<=k2) list.add(val);
		setIntToQueue(list,node.left,k1,k2);
		setIntToQueue(list,node.right,k1,k2);
	}
	
	public static class TreeNode {
		public int val;
		public TreeNode left, right;

		public TreeNode(int val) {
			this.val = val;
			this.left = this.right = null;
		}
	}
}
